// 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
// 二叉树的根是数组中的最大元素
// 左子树是通过数组中最大值左边部分构造出的最大二叉树
// 右子树是通过数组中最大值右边部分构造出的最大二叉树
// 通过给定的数组构建最大二叉树，并且输出这个树的根节点

// 时间复杂度：O(n)，n是数组的长度
// 空间复杂度：O(n)，递归栈的大小

function constructMaximumBinaryTree(arr) {
    if (!arr.length) {
        return null
    }
    let maxVal = arr[0]
    let maxIndex = 0
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > maxVal) {
            maxVal = arr[i]
            maxIndex = i
        }        
    }
    let root = new TreeNode(maxVal)
    root.left = constructMaximumBinaryTree(arr.slice(0, maxIndex))
    root.right = constructMaximumBinaryTree(arr.slice(maxIndex + 1))
    return root
}

function TreeNode(val) {
    this.val = val
    this.left = null
    this.right = null
}


let arr = [3, 2, 1, 6, 0, 5]
console.log(constructMaximumBinaryTree(arr))